package a13_Tree;

/**
 * @Author quan
 * @Description 二叉树的构建：底层用数组实现
 * @Date 2023/3/23 21:15
 */
public class MyBinTree {
    public class TreeNode{
        char val;
        TreeNode left;
        TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
    /**
     * 创建树
     */
    public TreeNode buildTree(){
        //创建8个树节点
        TreeNode node1 = new TreeNode('A');
        TreeNode node2 = new TreeNode('B');
        TreeNode node3 = new TreeNode('C');
        TreeNode node4 = new TreeNode('D');
        TreeNode node5 = new TreeNode('E');
        TreeNode node6 = new TreeNode('F');
        TreeNode node7 = new TreeNode('G');
        TreeNode node8 = new TreeNode('H');
        //创建子树的关系
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node3.left = node5;
        node3.right = node6;
        node6.left = node7;
        node6.right = node8;
        //返回根节点
        return node1;
    }
    /**
     * 前序遍历:  根 左 右
     */
    public void preOrder(TreeNode root) {
       //边界条件
        if(root == null){
            return;
        }
        //正常情况：根——>根的左节点——>根的右节点
        //根
        System.out.println(root.val);
        //左
        preOrder(root.left);
        //右
        preOrder(root.right);
    }

    /**
     * 中序遍历:  左 根 右
     */
    public void midOrder(TreeNode root) {
        //边界条件
        if(root == null){
            return;
        }
        //正常情况：根的左节点——>根——>根的右节点
        //左
        midOrder(root.left);
        //根
        System.out.println(root.val);
        //右
        midOrder(root.right);
    }
    /**
     * 后序遍历:  左  右  根
     */
    public void postOrder(TreeNode root) {
        //边界条件
        if(root == null){
            return;
        }
        //正常情况：根的左节点——>根的右节点——> 根
        //左
        postOrder(root.left);
        //右
        postOrder(root.right);
        //根
        System.out.println(root.val);
    }
    /**
     * 传入一颗以root为根的二叉树，就能求出该树的结点个数
     */
    public int treeNodeSize(TreeNode root) {
        //没有任何节点
        if(root == null){
            return 0;
        }
        //总结点=根+根的左节点+根的右节点
        return 1+treeNodeSize(root.left)+treeNodeSize(root.left);
    }
    /**
     * 传入一颗以root为根的二叉树，就能统计出当前这棵树的叶子结点的个数
     */
    public int leafNodes(TreeNode root) {
        //没有任何节点
        if(root==null){
            return 0;
        }
        //如果只有根节点一个
        if(root.left == null &&root.right == null){
            return 1;
        }
        // 总的叶子结点个数 = 左子树的叶子节点个数 + 右子树的叶子结点个数
        return leafNodes(root.left)+leafNodes(root.right);
    }
    /**
     * 传入一颗以root为根的二叉树，就能求出该树的高度
     */
    public int height(TreeNode root){
        //没有任何节点
        if(root==null){
            return 0;
        }
        // 总高度 = 1 + Math.max(左子树高度，右子树高度)
        return 1 + Math.max(height(root.left),height(root.right));
    }
    //测试类
    public static void main(String[] args) {
        MyBinTree tree = new MyBinTree();
        //创建一个树，获取根节点
        TreeNode root = tree.buildTree();
        //遍历树
        tree.preOrder(root);
        //测试总结点数
        System.out.println(tree.treeNodeSize(root));
        //测试叶子结点数
        System.out.println(tree.leafNodes(root));
        //测试高度
        System.out.println(tree.height(root));
    }
}
